package com.atguigu.graph;

import java.lang.management.GarbageCollectorMXBean;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class GraphDemo {
    public static void main(String[] args) {
        String[] vertexs=new String[]{"A","B","C","D","E"};

        Graph graph = new Graph(vertexs.length);
        for (String vertex : vertexs) {
            graph.addVertex(vertex);
        }
        // A-B, A-C, B-C, B-D, B-E
        graph.addEdge(0,1,1);
        graph.addEdge(0,2,1);
        graph.addEdge(1,2,1);
        graph.addEdge(1,3,1);
        graph.addEdge(1,4,1);

        graph.show();

        System.out.println("dfs");

        graph.dfs(0);

        System.out.println("bfs");

        graph.bfs();
    }
}

class Graph{
    // 顶点集合
    ArrayList<String> vertexs;
    // 边集合
    int[][] edges;
    // 边数目
    int edgeCount;

    boolean[] isVisible;

    public Graph(int vertexCount){
        vertexs=new ArrayList<>(vertexCount);
        edges=new int[vertexCount][vertexCount];
        edgeCount=0;
        isVisible=new boolean[vertexCount];
    }


    public void addVertex(String vertex){
        vertexs.add(vertex);
    }

    public void addEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        edgeCount++;
    }

    public int getVertexIndex(String vertex){
        return vertexs.indexOf(vertex);
    }

    public int getVertexCount(){
        return vertexs.size();
    }

    public int getEdgeCount(){
        return edgeCount;
    }

    public void show(){
        for(int[] eachEdges:edges){
            System.out.println(Arrays.toString(eachEdges));
        }
    }

    public int getNextVertexIndex(int parentIndex,int startIndex){
        for(int i=startIndex;i<vertexs.size();i++){
            if(edges[parentIndex][i]>0&&!isVisible[i]){
                return i;
            }
        }
        return -1;
    }

    public void dfs(int index){
        if(isVisible[index]){
            return;
        }
        System.out.println(vertexs.get(index)+"=>");
        isVisible[index]=true;

        // 访问子元素
        int tempIndex=index;
        while(true){
            tempIndex++;
            System.out.print(" read:"+tempIndex+" ");
            tempIndex=getNextVertexIndex(index,tempIndex);
            if (tempIndex!=-1) {
                dfs(tempIndex);
            }else{
                break;
            }
        }
    }

    public void bfs(){
        // 供遍历用的搜索节点
        String first;
        int vertexIndex;

        // 先遍历第一个, 并将之放到集合中
        LinkedList<String> tempList=new LinkedList();
        tempList.add(vertexs.get(0));

        boolean[] visibles=new boolean[getVertexCount()];
        visibles[0]=true;

        while(!tempList.isEmpty()){
            first = tempList.getFirst();
            vertexIndex = getVertexIndex(first);
            // 取出当前节点的所有相邻节点, 放入队列中
            int[] vertexIndex2Edge=edges[vertexIndex];
            for (int i = 0; i < vertexIndex2Edge.length; i++) {
                if(!visibles[i]&&vertexIndex2Edge[i]>0){
                    visibles[i]=true;
                    tempList.add(vertexs.get(i));
                }
            }

            // 删除定点元素
            String removeFirst = tempList.removeFirst();
            System.out.println(removeFirst+"=>");

        }
    }
}
